package com.yc.leetcode;

/**
 * 回文字符串
 */
public class Palindromic {
    public static void main(String[] args) {
        Palindromic t = new Palindromic();
//        System.out.println(t.m2("babad"));
//        System.out.println(t.m2("ccc"));
//        System.out.println(t.m3("cbbd"));
        System.out.println(t.m4("yoyilli"));
    }

    public void test() {

    }

    /**
     * 暴力解法
     */
    public String m1(String s) {
        String res = "";
        String sub = null;
        int max = 0;
        boolean subFlag = true;
        for (int i=0; i<s.length(); i++) {
            for (int j=i+max+1; j<s.length()+1; j++) {
                subFlag = true;
                for (int k=i; k<(i+j)/2; k++) {
                    if (s.charAt(k) != s.charAt(j+i-k-1)) {
                        subFlag = false;
                        break;
                    }
                }
                if (subFlag) {
                    res = s.substring(i,j);
                    max = j-i;
                }
            }
        }
        return res;
    }

    public String m2(String s) {
        String res = "";
        String sub = null;
        int max = 0;
        for (int i=0; i<s.length(); i++) {
            //循环往左右扩散1位
            for (int j=max/2; j<s.length(); j++) {
                //判断左右是否越界
                if (i+j > s.length()) {
                    break;
                }
                //奇数扩散（中心点）
                if (i-j >= 0) {
                    sub = s.substring(i-j,i+j+1);
                    if (isPalindrome(sub)) {
                        res = sub;
                        max = j*2+1;
                        continue;//如果奇数成功了，偶数就不用试了，因为偶数少一位
                    }

                }


                //偶数扩散 至少是2
                if (j > 0 && i-j+1 >= 0) {
                    if (j*2 > max) {
                        sub = s.substring(i-j+1,i+j+1);
                        if (isPalindrome(sub)) {
                            res = sub;
                            max = j*2;
                        }
                    }
                } else {
                    break;
                }


            }

        }
        return res;
    }

    //验证是否是回文字符串
    public boolean isPalindrome(String s) {
        for (int i=0; i<s.length()/2; i++) {
            if (s.charAt(i) != s.charAt(s.length()-i-1)) {
                return false;
            }
        }
        return true;
    }

    //中心扩散
    public String m3(String s) {
        int max = 0;
        int start = 0;
        int end = 0;

        int left_j=0;int right_j=0;
        int left_o=0;int right_o=0;

        boolean j_flag = false;boolean o_flag = false;

        for (int i=0; i<s.length()-1; i++) {//中心
            j_flag = false;
            o_flag = false;
            //奇数
            left_j=right_j=i;
            while(left_j >= 0 && right_j < s.length() &&
                    s.charAt(left_j) == s.charAt(right_j)) {
                left_j--;
                right_j++;
                j_flag = true;
            }
            if (j_flag) {//进循环了，回退一格
                left_j++;
                right_j--;
            }

            //偶数
            left_o=i;right_o=i+1;
            while(left_o >= 0 && right_o < s.length() &&
                    s.charAt(left_o) == s.charAt(right_o)) {
                left_o--;
                right_o++;
                o_flag = true;
            }
            if (o_flag) {//进循环了，回退一格
                left_o++;
                right_o--;
            } else {//偶数没进循环，默认也多了一格，end-1
                right_o--;
            }


            if (right_j-left_j > right_o-left_o) {
                if (right_j-left_j+1 > max) {
                    max = right_j-left_j+1;
                    start = left_j;
                    end = right_j;
                }
            } else {
                if (right_o-left_o+1 > max) {
                    max = right_o-left_o;
                    start = left_o;
                    end = right_o;
                }

            }


        }
        return s.substring(start, end+1);
    }

    //动态规划
    public String m4(String s) {
        if (s.length() < 2) {
            return s;
        }

        int max = 0;
        int start = 0;
        int end = 0;
        //单个boolean变量和int一样，占4个字节。但在数组里，boolean占1个字节
        boolean[][] dp = new boolean[s.length()][s.length()];//

        //起始位置i倒序遍历，结尾j正序。
        //保证下面dp[i][j] = dp[i+1][j-1]成立（dp[i+1][j-1]一定先于dp[i+1][j-1]出现）
        for (int i=s.length()-1; i>=0; i--) {
            for (int j = i; j < s.length(); j++) {//结束位置
                if (i==j) {
                    dp[i][j] = true;
                }

                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if(j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //这句话：如果最边上的相等，那么就看里面的是不是回文。如果是，则是。如果不是，则不是。
                        //如果最边上的不相等，那么就不看里面一层。
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if (dp[i][j] && j-i+1 > max) {
                    max = j-i+1;
                    start = i;
                    end = j;
                }

            }

        }

        return s.substring(start, end+1);
    }


}
